package week_1.homework;
import java.util.Scanner;

public class IntergerLinkedlistExample {
    //（1）通过键盘输入一些整数，建立一个链表。
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        System.out.println("请输入一个整数:");
        int num1 = scan.nextInt();
        IntegerLinkedlist Head = new IntegerLinkedlist(num1);
        String reply = "";
        System.out.println("您是否还要继续输入？请输入y/n");
        reply = scan.next();
        if(reply.equalsIgnoreCase("y")) {
            do {
                System.out.println("请继续输入一个整数:");
                int num2 = scan.nextInt();
                System.out.println("您是否还要继续输入？请输入y/n");
                reply = scan.next();
                IntegerLinkedlist linkedlist = new IntegerLinkedlist(num2);
                InsertNode(Head, linkedlist);
            }
            while (reply.equalsIgnoreCase("y"));
        }
        System.out.println("用户输入的整数链表：");
        PrintLinkedlist(Head);
        System.out.println();
        System.out.println("排序后的整数链表为：");
        bubbleSort(Head);//用冒泡排序法。
        PrintLinkedlist(Head);
        System.out.println();
    }

    //（2）实现节点插入、删除、输出等操作
    //链表的输出方法。
    public static void PrintLinkedlist(IntegerLinkedlist Head) {
        IntegerLinkedlist node = Head;//链表的头不能动。
        while (node != null) {
            System.out.print(" " + node.number);
            node = node.next;
        }
    }

    //头插法的方法。
    public static void InsertNode1(IntegerLinkedlist Head, IntegerLinkedlist node) {
        node.next = Head;
        Head = node;
        System.out.println("" + Head.number);
    }

    //尾插法的方法。
    public static void InsertNode(IntegerLinkedlist Head, IntegerLinkedlist node) {
        IntegerLinkedlist temp = Head;
        //遍历链表，找到链表末尾。
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = node;
    }

    //链表的中间插入。
    public static void InsertNode(IntegerLinkedlist Head, IntegerLinkedlist node1, IntegerLinkedlist node2) {
        IntegerLinkedlist point = Head;
        while ((point.number != node1.number) & point != null) {
            point = point.next;
        }
        if (point.number == node1.number) {
            node1.next = point.next;
            point.next = node2;
        }
    }

    //链表的删除方法。
    public static void Deletenode(IntegerLinkedlist Head, IntegerLinkedlist node) {//这里的node要指向需要删除对象的前一个节点。
        IntegerLinkedlist prenode = Head, currentnode = Head;
        while (prenode != null) {
            if (currentnode != node) {
                prenode = currentnode;
                currentnode = currentnode.next;
            } else {
                break;
            }
        }
        prenode.next = currentnode.next;
    }

    //(3)使用冒泡排序法或者选择排序法根据数值大小对链表进行排序。
    //链表的选择排序法。
    public static IntegerLinkedlist selectionSort(IntegerLinkedlist Head) {
        //记录每次循环的最小值
        int temp ;
        IntegerLinkedlist curNode = Head;
        while (curNode != null) {
            /**
             * 内重循环从当前节点的下一个节点循环到尾节点，
             * 找到和外重循环的值比较最小的那个，然后与外重循环进行交换
             */
            IntegerLinkedlist nextNode = curNode.next;
            while (nextNode != null) {
                //比外重循环的小值放到前面
                if (nextNode.number < curNode.number) {
                    temp = nextNode.number;
                    nextNode.number = curNode.number;
                    curNode.number = temp;
                }
                nextNode = nextNode.next;
            }
            curNode = curNode.next;
        }
        return Head;
    }
    //链表的冒泡排序法。
    public static IntegerLinkedlist bubbleSort(IntegerLinkedlist Head){
        if(Head == null || Head.next == null)  //链表为空或者仅有单个结点
            return Head;
        IntegerLinkedlist cur = null, tail = null;
        cur = Head;

        while(cur.next != tail){
            while(cur.next != tail){
                if(cur.number > cur.next.number){
                    int tmp = cur.number;
                    cur.number = cur.next.number;
                    cur.next.number = tmp;
                }
                cur = cur.next;
            }

            tail = cur;  //下一次遍历的尾结点是当前结点(仔细琢磨一下里面的道道)
            cur = Head;     //遍历起始结点重置为头结点
        }

        return Head;
    }
}
